package leecode.LinkedList.DoublePoint;

/**
 * 数学题，题解：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
 */
public class DetectCycle {
      class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }

        if(fast==null || fast.next==null){
            return null;
        }else{
            ListNode ptr=head;
            while(slow!=ptr){
                slow = slow.next;
                ptr = ptr.next;
            }
            return ptr;
        }
    }
}
